package code;

public class 剑指offer12 {
    final static int[][] dir=new int[][]{
            {-1,0},{1,0},{0,-1},{0,1}
    };
    int m,n;
    boolean[][] vis;
    public boolean check(int nr,int nc){
        if(nr>=m||nr<0||nc>=n||nc<0||vis[nr][nc]==true){
            return false;
        }
        return true;
    }
    public boolean search(char[][] board,int row,int col,char[] word,int index){
        if(index==word.length){
            return true;
        }
        for(int i=0;i<4;++i){
            int nr=row+dir[i][0];
            int nc=col+dir[i][1];
            if(check(nr,nc)&&word[index]==board[nr][nc]){
                vis[nr][nc]=true;
                if(search(board,nr,nc,word,index+1)){
                    return true;
                }
                vis[nr][nc]=false;
            }
        }
        return false;
    }
    public boolean exist(char[][] board, String word) {
        char[] wor=word.toCharArray();
        this.m=board.length;
        this.n=board[0].length;
        for(int i=0;i<board.length;++i)
            for(int j=0;j<board[0].length;++j){
                if(board[i][j]==wor[0]){
                    vis[i][j]=true;
                    if(search(board,i,j,wor,1))return true;
                    vis[i][j]=false;
                }
            }
        return false;
    }
}
